Reverse Integer || Reverse Bit

发表于

Reverse Integer

Question

Reverse digits of an integer.

Example1: x = 123, return 321

Example2: x = -123, return -321

Analysis

越界判断：

tmp加上tail后看是否还能变回原来的数字，不可直接利用int型的加和来判断越界（tmp*10+tail>Integer.MAX_VALUE）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int reverse(int x) {
        boolean flag=false;
      	if(x<0)	flag=true;
      	x=Math.abs(x);
        int res=0;
     	int tmp=0;
      	while(x!=0){
          	int tail=x%10;
          	tmp=tmp*10+tail;
          	if((tmp-tail)/10!=res)
                return 0;  	
            res=tmp;
          	x=x/10;
      	}
      	if(flag)	return -res;
      	return res;
    }
}

Reverse Bit

Question

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Analysis

  • 每次取出数字n的最后一位给res，res在前31位的时候不断左移
  • 优化后，将32-bit分为四段，利用map来保存倒转的结果

LeetCode Discuss Answer

中文参考

Code

Basic Version

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res=0;
        for(int i=0;i<32;i++){
            res+=n&1;
            n>>>=1;
            if(i<31)
                res<<=1;
        }
        return res;
    }
}

Optimized Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    // you need treat n as an unsigned value
    public final Map<Byte,Integer> cache=new HashMap<Byte,Integer>();
    public int reverseBits(int n) {
        int res=0;
        byte[] bytes=new byte[4];
        for(int i=0;i<4;i++){
            bytes[i]=(byte)((n>>>8*i)&0xFF);
        }
        for(int j=0;j<4;j++){
            int tmp=munipulation(bytes[j]);
            res+=tmp;
            if(j<3)
                res<<=8;
        }
        return res;
    }
    
    public int munipulation(Byte b){
        Integer value=cache.get(b);
        if(value!=null){
            return value;
        }
        value=0;
        for(int i=0;i<8;i++){
            value+=(b>>>i)&1;
            if(i<7)
                value<<=1;
        }
        cache.put(b,value);
        return value;
    }
}